//
// Description: 5839. 移除石子使总数最小
// Created by Loading on 2021/8/8.
//

#include <bits/stdc++.h>

using namespace std;

// 使用 make_heap
int minStoneSum_MakeHeap(vector<int> &piles, int k) {
    // 生成大顶堆
    make_heap(piles.begin(), piles.end());
    while (k--) {
        // 弹出大顶堆堆顶元素
        pop_heap(piles.begin(), piles.end());
        piles.back() -= piles.back() / 2;
        // 处理完毕重新推进大顶堆
        push_heap(piles.begin(), piles.end());
    }

    return accumulate(piles.begin(), piles.end(), 0);
}

// 使用 priority_queue
int minStoneSum(vector<int> &piles, int k) {
    // 求和
    int sum = accumulate(piles.begin(), piles.end(), 0);
    // 优先级队列
    priority_queue<int> q;
    for (auto &x : piles) {
        q.emplace(x);
    }
    while (k--) {
        // 每次取最大，减半后加入队列
        int x = q.top();
        q.pop();
        sum -= x / 2;
        x -= x / 2;
        q.emplace(x);
    }

    return sum;
}

int main() {
    vector<int> piles = {4, 3, 6, 7};
    int k = 3;
    cout << minStoneSum(piles, k) << endl;
    cout << minStoneSum_MakeHeap(piles, k) << endl;
}